﻿#include <iostream>
using namespace std;

//排序子序列
//https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471

//const int N = 1e5 + 5;
//int n;
//int arr[N];
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> arr[i];
//
//	int i = 0, ret = 0;
//	while (i < n)
//	{
//		if (i == n - 1)
//		{
//			ret++;
//			break;
//		}
//
//		if (arr[i] > arr[i + 1])
//		{
//			while (i < n - 1 && arr[i] >= arr[i + 1])
//				i++;
//			ret++;
//		}
//		else if (arr[i] < arr[i + 1])
//		{
//			while (i < n - 1 && arr[i] <= arr[i + 1])
//				i++;
//			ret++;
//		}
//		else
//			while (arr[i] == arr[i + 1])i++;
//		i++;
//	}
//	cout << ret << endl;
//}


// 削减整数（贪⼼+数学）
// https://ac.nowcoder.com/acm/problem/219038

//贪心：尽可能减去之前数（a）的二倍
//只有剩余数(h)是2a的整数倍，才能恰好减到0，即 h % 2a == 0

//int func(int h)
//{
//    int ret = 0, a = 1;
//    while (h)
//    {
//        h -= a;
//        ret++;
//        if (h % (2 * a) == 0)
//            a *= 2;
//    }
//    return ret;
//}
//
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {        
//        int h;
//        cin >> h;
//        cout << func(h) << endl;
//    }
//}
